package leetcode_ago.LinearList;

/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
public class Num206_reverseList {
    /**
     * 3.递归解决
     */
    public ListNode reverseList(ListNode head) {
      if(head==null||head.next==null){
          return head;
      }
      //已知头节点，反转链表，返回反转后的链表
        ListNode temp=head.next;//先保存待处理节点的下一个节点
        //反转子链表,返回子链表的头节点
        ListNode newHead=reverseList(head.next);
        //处理头和第二个节点的关系，将next.next=head;head.next=null[反转步骤]
        temp.next=head;
        head.next=null;
        return newHead;
    }

    /**
     * 2.原地移动
     * next不再指向后继而是指向前驱
     * cur:当前要处理的节点，prev:前驱节点
     */
//    public ListNode reverseList(ListNode head) {
//        if(head==null||head.next==null){
//            return head;
//        }
//        //当前需要反转的节点
//        ListNode cur=head;
//        //当前需要反转的节点的前驱
//        ListNode prev=null;//头结点的前驱为null
//        while(cur!=null){
//            //临时变量临时保存cur的下一位
//            ListNode temp=cur.next;
//            cur.next=prev;
//            //更新条件
//            prev=cur;
//            cur=temp;
//        }
//        return prev;//cur为空的此时prev正好是新的链表的头节点
//    }
    /**
     * 1.头插法
     * @param head
     * @return
     */
//    public ListNode reverseList(ListNode head) {
//        if(head==null||head.next==null){
//            return head;
//        }
//        //构建虚拟头节点
//        ListNode dummyHead=new ListNode(5001);
//        //边遍历原链表边进行新链表的头插操作
//        while(head!=null){
//            ListNode cur=new ListNode(head.val);
//            cur.next=dummyHead.next;
//            dummyHead.next=cur;
//            head=head.next;
//        }
//        return dummyHead.next;
//    }
}
